package com.sean.sort;

/**
 * 插入排序：直接插入排序，shell 排序
 */
public class InsertSort {
    /**
     * 插入排序原理：
     *      逐个处理元素，将每个新元素与已经排好序的元素进行比较，
     *      找到插入的位置，移出空位，插入元素。
     * @param array 待排序的数组
     */
    public static void directInsertSort(int[] array){
        long start = System.nanoTime();
        if(array.length <= 1){
            return;
        }
        for(int right = 1; right < array.length; right++){
            int temp = array[right];
            int left = right - 1;
            while(left >= 0 && array[left] > temp){
                array[left + 1] = array[left];
                left --;
            }
            array[left + 1] = temp;
        }
        long end = System.nanoTime();
        System.out.println("直接插入排序用时： " + (end - start) + "ns");
    }

    /**
     * 希尔排序原理：
     *      分组的直接插入排序
     * @param array 待排序的数组
     */
    public static void shellSort(int[] array){
        long start = System.nanoTime();
        if(array.length <= 1){
            return;
        }
        for(int delta = array.length / 2; delta > 0; delta /= 2){
            for(int right = delta; right < array.length; right++){
                int temp = array[right];
                int left = right - delta;
                while(left >= 0 && array[left] > temp){
                    array[left + delta] = array[left];
                    left -= delta;
                }
                array[left + delta] = temp;
            }
        }
        long end = System.nanoTime();
        System.out.println("希尔排序用时： " + (end - start) + "ns");
    }

    public static void main(String[] args) {
        final int _10w = 100000;
        // 直接插入排序用时： 28700ns
        int [] test1 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test1[j] = i;
        }
        InsertSort.directInsertSort(test1);

        // 希尔排序用时： 6700ns
        int [] test2 = new int[_10w];
        for(int i = _10w, j = 0; i > 0; i--, j++){
            test2[j] = i;
        }
        InsertSort.shellSort(test2);
    }
}
